#include <stdio.h>
#include <stdlib.h>

#define SIZE 5

typedef struct Table {
    //使用数组结构来申请一块预定义的空间,这里是不是一个普通的指针，而是一个动态的数组
    int *head;
    //顺序表使用的长度
    int len;
    //顺序表分配的存储容量
    int size;
} table;

//初始化顺序表
table tableInit() {
    table t;
    t.head = (int *) malloc(SIZE * sizeof(int));
    if (!t.head) {
        printf("初始化失败");
        exit(0);
    }
    t.len = 0; //空表的长度初始化0
    t.size = SIZE; //表的大小初始存储空间
    return t;
}

//展示顺序表的数据
void displayTable(table t) {
    printf("顺序表的长度是: %d \n", t.len);
    for (int i = 0; i < t.len; ++i) {
        printf("%d ", t.head[i]);
    }
    printf("\n");
}

//addTable 为顺序表插入元素
//table t 顺序表
//int location 插入数据的位置
//int elem 插入的数据
table addTable(table t, int location, int elem) {
    //为顺序表插入数据其实就是找到特定位置，然后把位置上的已有的数据往后挪动一个位置

    //首先判断插入是否超过了顺序表的长度
    if (location > t.len + 1 || location < 1) {
        printf("插入位置错误");
        return t;
    }

    //判断顺序表分配的大小是否满足需要，不足够的话重写分配内存
    if (t.len == t.size) {
        t.head = (int *) realloc(t.head, (t.size + 1) * sizeof(int));
        if (!t.head) {
            printf("分配内存失败");
            return t;
        }
        //记录分配的大小
        t.size += 1;
    }

    for (int i = t.len - 1; i >= location - 1; --i) {
        t.head[i + 1] = t.head[i];
    }

    t.head[location - 1] = elem;
    t.len++;
    return t;
}

//table t 顺序表
//int location 要删除的位置
//删除一个元素，则是把这个要删除元素后面的元素全部往前移动一个位置
table delTable(table t, int location) {
    //判断要删除的位置是否正确
    if (location > t.len || location < 1) {
        printf("要删除元素的位置有错误");
        exit(1);
    }
    for (int i = location; i < t.len; i++) {
        t.head[i - 1] = t.head[i];
    }
    t.len--;

    return t;
}

//查找数据
//table t 顺序表
//int elem 要查找的元素
//这里使用顺序查找实现,返回找到数据所在的位置
int selectTable(table t, int elem) {
    for (int i = 0; i < t.len; ++i) {
        if (t.head[i] == elem) {
            return i;
        }
    }

    //没有找到数据那么返回-1
    return -1;
}

table amendTable(table t,int oldElem,int elem) {

    int location = selectTable(t,oldElem);
    if(location != -1) {
        t.head[location] = elem;
    } else {
        printf("没有找到要修改的元素");
        exit(1);
    }

    return t;
}

int main() {
    printf("Hello, World!\n");
    table t = tableInit();
    for (int i = 1; i <= t.size; ++i) {
        t.head[i - 1] = i;
        t.len++;
    }
    displayTable(t);

    //增加一个元素
    printf("在第%d位增加一个元素：%d \n",2,10);
    t = addTable(t, 2, 10);
    displayTable(t);

    //删除一个元素
    printf("删除第 %d 位的一个元素 \n",2);
    t = delTable(t, 2);
    displayTable(t);

    //查找一个元素
    int findNum = 3;
    int location = selectTable(t,findNum);
    printf("期望值: %d,找到的位置: %d,实际值: %d,结果是(%s)。 \n",
           findNum,location,t.head[location],findNum == t.head[location] ?  "正确的":"错误的");

    //替换元素
    printf("替换第%d个位置的数据，替换为：%d\n",5,4);
    t = amendTable(t,5,4);
    displayTable(t);

    return 0;
}
